package pers.whj.sort;

public class HeapSort<T> extends Sort<T> {
    public HeapSort(T[] data) throws SortException {
        super(data);
    }

    public HeapSort(T[] data, Compare<T> compare) throws SortException {
        super(data, compare);
    }

    @Override
    public void sort(int left, int right) throws SortException {
        sort(mData, mCompare, left, right);
    }

    public static <E> void sort(E[] data) throws SortException {
        sort(data, null);
    }

    public static <E> void sort(E[] data, Compare<E> compare) throws SortException {
        sort(data, compare, 0, data == null ? 0 : data.length - 1);
    }

    public static <E> void sort(E[] data, Compare<E> compare, int left, int right) throws SortException {
        check(data, compare, left, right);
        for (int i = (right - left - 1) / 2; i >= 0; i--) {
            siftDown(data, compare, i, right - left, left);
        }
        for (int i = right - left; i > 0; i--) {
            E temp = data[left];
            data[left] = data[left + i];
            data[left + i] = temp;
            siftDown(data, compare, 0, i - 1, left);
        }
    }

    private static <E> void siftDown(E[] data, Compare<E> compare, int start, int end, int offset) {
        int i = start;
        int j = 2 * i + 1;
        E temp = data[i + offset];
        while (j <= end) {
            if (j < end && !compare.swap(data[j + offset], data[j + offset + 1])) {
                j++;
            }
            if (compare.swap(temp, data[j + offset])) {
                break;
            } else {
                data[i + offset] = data[j + offset];
                i = j;
                j = 2 * j + 1;
            }
        }
        data[i + offset] = temp;
    }
}